package leetcode.题库.动态规划;

/**
 * 分隔数组以得到最大和
 *
 * @author yanzhenming
 * @date 2023/4/19  12:48
 */

/**
 * 描述
 *
 * 给你一个整数数组 arr，请你将该数组分隔为长度 最多 为 k 的一些（连续）子数组。分隔完成后，每个子数组的中的所有值都会变为该子数组中的最大值。
 *
 * 返回将数组分隔变换后能够得到的元素最大和。本题所用到的测试用例会确保答案是一个 32 位整数。
 *
 */

/**
 * 思路
 *
 * 动态规划
 * 计算每个位置的最大和，当前位置等于最后一个位置到i-k+1位置之间各种情况的最大值
 */
public class Solution1043 {

    public static void main(String[] args) {
        int[] arr= new int[]{1,15,7,9,2,5,10};
        System.out.println(maxSumAfterPartitioning(arr, 3));
    }

    public static int maxSumAfterPartitioning(int[] arr, int k) {
        int[] dp = new int[arr.length+1];
        dp[0] = 0; dp[1] = arr[0];
        for (int i = 1; i < arr.length; i++) {
            int max = Integer.MIN_VALUE;
            for (int j = i; j >= 0 && j >= i - k + 1; j--) {
                max = Math.max(max, arr[j]);
                dp[i+1] = Math.max(dp[i+1], max*(i-j+1) + dp[j]);
            }
        }
        return dp[arr.length];
    }

}
